1. Field of the Invention
This invention relates generally to the transfer of information segments across a broadband switch and, more particularly, to a system and method for sorting information segments in a earliest deadline first (EDF) queue based upon information segment field rankings.
2. Description of the Related Art
As noted in U.S. Pat. No. 5,608,662 (Large et al.), there are various situations and various types of communication signal paths in which it would be desirable to enable a selection of data to be processed and to cause other data to be ignored or perhaps processed differently. One example is a broadcast data network, i.e., a network wherein data are transmitted generally to a number of subscriber stations. The data are subdivided into data set groupings, such as a number of consecutive bytes typically including leading and/or trailing marker or information bytes or the like, which groupings are termed “packets.”
A packet is a sequence of bytes delivered by the communication line that are rendered distinct from other sequences of bytes, according to a protocol applied when the bytes are encoded and decoded. Packet techniques are well known and include, for example, the EtherNet protocol (IEEE standard 802.3) and commercial packet protocols such as the Synchronous Data Link protocol (SDLC) and X.25. An external circuit monitors the incoming communication line and determines when the packet begins. Bytes of the packet are then processed until packet reception is complete.
Commercially available circuits and interfaces are known for performing the tasks of recognizing the beginning of a packet and processing bytes until complete, for example as known from a byte count, end marker or the like. The generic function of receiving packets is thus known. However, once a packet or sequence of bytes is extracted from the communication network, there are a variety of possibilities as to how the encoded data are to be processed.
The quickest method of sorting information segments is to use a “broadcast”-based sorting method. In this method, an insert or an extract operation can be communicated to every register in the queue simultaneously. Information segments can likewise be inserted or extracted, from register to register, in a single operation. However, the broadcast sorting method has difficulties associated with it. A hardwire connection must be made to each stage. This makes for hardware design problems and associated long interconnect delay. Further, it is difficult to expand or scale such a design because global interconnects do not scale well especially as the technology shrinks to smaller feature sizes.
On the other hand, a systolic array relies upon communications between neighboring stage registers to insert or extract information segments. Thus, the design is flexible and can be scaled. However, the more limited stage-to-stage communication requires relaying information segments stage-to-stage. For example, extraction is done in two steps: One step to extract an information segment from a stage and one step to fill the empty stage from a neighboring stage so that a next extraction can be done.
It would be advantageous if a system existed for more efficiently handling information segments in a systolic array.
It would be advantageous if the stages in a systolic array worked as teams to speed the sorting process.
It would be advantageous if a systolic array sorting system could operate at a higher processing rate. Specifically, it would be advantageous if information to be sorted could be inserted at twice the rate at which it is extracted.